package com.jietuo.class03;

import java.util.Arrays;

/**
 * @author zhangx & jietuo_zx@163.com
 * @version 1.0
 * @date 2024/3/3
 * @description: 快排
 */
public class Code04_QuickSort {

    public static void main(String[] args) {
        int[] arr = new int[]{2, 4, 3, 7, 1, 9};
        System.out.println(Arrays.toString(arr));
        quickSort1(arr);
        System.out.println(Arrays.toString(arr));
    }

    private static void quickSort1(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        process1(arr, 0, arr.length - 1);
    }

    private static void process1(int[] arr, int left, int right) {
        if (left >= right) {
            return;
        }
        // 先找出一个随机数，然后和最后一位交换
        int randomNum = (int) Math.random() * (right - left + 1);
        swapArr(arr, randomNum + left, right);
        int[] equalArea = partition(arr, left, right);
        process1(arr, left, equalArea[0] - 1);
        process1(arr, equalArea[1] + 1, right);
    }

    private static int[] partition(int[] arr, int left, int right) {
        int leftBuf = left - 1;
        int rightBuf = right;
        int index = left;
        while (index < rightBuf) {
            if (arr[index] == arr[right]) {
                // 找到相等的值，index右移即可
            } else if (arr[index] < arr[right]) {
                // 找到小于目标值，则与左缓存区域的右一个位置交换，并将index右移
                swapArr(arr, ++leftBuf, index++);
            } else if (arr[index] > arr[right]) {
                // 找到大于目标值，则需要与右缓存区域的左一个位置交换，而交换到index上的这个数，还未比较过，所以index不动
                swapArr(arr, --rightBuf, index);
            }
        }
        // 全部交换完成之后，需要将最后一位right与右缓存区域的交换
        swapArr(arr, rightBuf, right);
        return new int[]{leftBuf + 1, rightBuf};
    }

    private static void swapArr(int[] arr, int i, int right) {
        int temp = arr[i];
        arr[i] = arr[right];
        arr[right] = temp;
    }
}
